package org.example.sort;

import com.google.gson.Gson;

/**
 * 归并排序
 */
public class MergeSort {
    private int[] B;

    public MergeSort(int n) {
        B = new int[n];
    }

    /**
     * 将两个有序的数列合并为一个有序的数列
     * @param A
     * @param low
     * @param mid
     * @param high
     */
    public void merge(int[] A, int low, int mid, int high) {
        int i, j, k;
        // 将A中所有的元素复制到B对应的位置中
        for (k = low; k <= high; k++) {
            B[k] = A[k];
        }

        for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
            // 将较小的复制到A中
            if (B[i] <= B[j]) {
                A[k] = B[i++];
            } else {
                A[k] = B[j++];
            }
        }
        // 复制比较后剩下的部分元素
        while (i <= mid) {
            A[k++] = B[i++];
        }
        while (j <= high) {
            A[k++] = B[j++];
        }
    }

    public void mergeSort(int[] A, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2; // 从中间划分
            mergeSort(A, low, mid); // 对左半部分归并排序
            mergeSort(A, mid + 1, high); // 对右半部分归并排序
            merge(A, low, mid, high); // 将左右排好序的两个列表进行归并
        }
    }
}
